'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-01 15:17:10
'''
#
# @lc app=leetcode.cn id=1201 lang=python3
#
# [1201] 丑数 III
#

# @lc code=start
class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        # 居然是二分法，只要知道了查找数字是第几个丑数即可。
        def comman(x, y):
            minn = min(x, y)
            maxx = max(x, y)
            while minn:
                tmp = maxx%minn
                maxx = minn
                minn = tmp
            return x*y//maxx
        com_ab, com_ac, com_bc  = comman(a, b), comman(a, c), comman(b, c)
        com_abc = comman(com_ab, c)
        def cUgly(x):
            return x//a+x//b+x//c-x//com_ab-x//com_ac-x//com_bc+x//com_abc
        # print(cUgly(8))
        begin, end = 1, 2e9
        while begin<end:
            med = (begin+end)//2
            cu = cUgly(med)
            if cu>n:
                end = med-1
            elif cu<n:
                begin = med+1
            else:
                if not med%a or (not med%b) or (not med%c):
                    return int(med)
                else:
                    end = med-1

        return int(begin)
# @lc code=end

if __name__ == "__main__":
    solution = Solution()
    n, a, b, c = 4, 2, 3, 4
    print(solution.nthUglyNumber(n, a, b, c))